#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/11/29 22:03
# @USER    : Shengji He
# @File    : LargestPerimeterTriangle.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def largestPerimeter(self, A: List[int]) -> int:
        """
        Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area,
        formed from 3 of these lengths.

        If it is impossible to form any triangle of non-zero area, return 0.

        Example 1:
            Input: [2,1,2]
            Output: 5
        Example 2:
            Input: [1,2,1]
            Output: 0
        Example 3:
            Input: [3,2,3,4]
            Output: 10
        Example 4:
            Input: [3,6,2,3]
            Output: 8

        Note:
            1. 3 <= A.length <= 10000
            2. 1 <= A[i] <= 10^6

        :param A:
        :return:
        """
        A.sort()
        for i in range(len(A) - 1, 1, -1):
            if (A[i - 2] + A[i - 1]) > A[i]:
                return A[i - 2] + A[i - 1] + A[i]
        return 0


if __name__ == '__main__':
    S = Solution()
    A = [3, 6, 2, 3]
    print(S.largestPerimeter(A))
    print('done')
